import java.util.PriorityQueue;

public class Main {
    public static void main(String[] args) {
//        System.out.println(new Solution().largestSumAfterKNegations(new int[]{4,2,3}, 1));
        System.out.println(new Solution().largestSumAfterKNegations(new int[]{-1, -4}, 3));
        System.out.println(new Solution().largestSumAfterKNegations(new int[]{3,-1,0,2}, 3));
        System.out.println(new Solution().largestSumAfterKNegations(new int[]{2,-3,-1,5,-4}, 2));
    }
}

//其他方法：先排序（或者用哈希表存-100到100的数，免去排序）
class Solution {
    public int largestSumAfterKNegations(int[] nums, int k) {
        PriorityQueue<Integer> maxHeap = new PriorityQueue<>((a, b) -> b - a);
        int minKSum = 0;
        int otherSum = 0;
        for (int num : nums) {
            if (maxHeap.size() == k) {
                if (maxHeap.peek() < num) {
                    otherSum += num;
                    continue;
                }
                int v = maxHeap.poll();
                otherSum += v;
                minKSum -= v;
            }
            maxHeap.offer(num);
            minKSum += num;
        }

        int minNonNegative = 10000;
        int negativeSum = minKSum;
        while (!maxHeap.isEmpty() && maxHeap.peek() >= 0) {
            int num = maxHeap.poll();
            minNonNegative = num;
            negativeSum -= num;
            otherSum += num;
        }
        int result = otherSum - negativeSum;
        if ((k - maxHeap.size()) % 2 == 1) {
            if (!maxHeap.isEmpty() && -maxHeap.peek() < minNonNegative) {
                result += maxHeap.peek() + maxHeap.peek();
            } else {
                result -= minNonNegative + minNonNegative;
            }
        }
        return result;
    }
}